package com.itheima11;

import java.util.Arrays;

/**
 * @author Xiao
 * @date 2021/7/20
 */
public class FactorialDemo03 {
    /**
     * 快排
     *      1.从右开始找比基准数小的；
     *      2.从左开始找比基准数大的；
     *      3.交换两个值的位置
     *      4.红色继续往左找，蓝色继续往右找，知道两个箭头指向同一个索引为止；
     *      5.基准数归位。
     */
    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        int left = 0;
        int right = arr.length - 1;
        quitSort(arr, left, right);
        System.out.println(Arrays.toString(arr));
                /*int start = 0;
        int end = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[end] > arr[0]) {
                end--;
            }
            if (arr[start] < arr[0]) {
                start++;
            }
            if (arr[start] > arr[0] && arr[end] < arr[0]) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
            if (start == end) {
                int temp = arr[0];
                arr[0] = arr[start];
                arr[start] = temp;
            }
        }*/
    }

    public static void quitSort(int[] arr, int left, int right) {
        int left0 = left;
        int base = arr[left0];
        while (left != right) {
            while (arr[left] < base && left < right) {
                left++;
            }
            while (arr[right] > base && left < right) {
                right--;
            }
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        int temp = base;
        base = arr[left];
        arr[left] = temp;
    }
}
